TopK问题用快排和堆排的复杂度分别是多少？

2024-06-14 16:01| 来源: 网络整理| 查看: 265

关于TopK问题

TopK问题就是在一堆数据里面找到前 K 大(当然也可以是前 K 小)的数

常规方法，完全排序

先完全排序后取topK，这种方法需要将数据完全排序，不适用于大数据量

利用快排 3.1 解决思路

借鉴快排的思想，在patiton中数组会分为三个部分，我们只要与index相比较就可以得出TopK是在左边部分还是右边部分，因此不需要全部排序

public class Solution { //要求的第k个数 int k; List res = new ArrayList(); public List GetLeastNumbers(int [] input, int k) { if (input.length if(l > r) { return ; } int index = patiton(arr, l, r); //此处判断就是为了变成局部排序 if(index == k - 1) { for (int i = 0; i quick_sort(arr, l ,index - 1); }else { quick_sort(arr, index + 1, r); } } private int patiton(int[] arr, int l, int r) { int tmp=arr[l]; while(l r--; } arr[l]=arr[r]; while (l ArrayList res = new ArrayList(); public ArrayList GetLeastNumbers_Solution(int [] input, int k) { if (input.length public int compare(Integer a, Integer b) { return b - a; } }); int len = input.length; if(len if(queue.size() if(queue.peek() > input[i]) { queue.poll(); queue.add(input[i]); } } } return new ArrayList(queue); } } 4.2 复杂度分析

首先需要对K个元素进行建堆，时间复杂度为O(k)，然后要遍历数组,最坏的情况是，每个元素都与堆顶比较并排序，需要堆化n次所以是O(nlog(k))，因此总复杂度是O(k+nlog(k));

5.小结

快排和堆排解决topK问题的复杂度其实面试中有被问过，有不少面试者直接答的快排和堆排的复杂度，但其实是不一样的，在TopK问题中，快排和堆排的复杂度分别问O(n)和O(k+nlog(k))

通过对比可以发现，堆排的优势是只需读入K个数据即可，可以实现来一个数据更新一次，能够很好的实现数据动态读入并找出TopK。

【本文地址】

公司简介

联系我们